package com.my.test.array;

/**
 * A shiftted interger array like {1,2,3,4,5,6,7,8,9} is already sorted.
 * Assuming the array is splitted into 2 parts and put the latter part before
 * the former part, ie: {7,8,9,1,2,3,4,5,6}, here need to find an item in array.
 * 
 * @author Wormholes
 * 
 */
public class ShifttedArraySearch {

	public static int shiftArraySearch(int n, int[] d, int start, int end) {
		if (start == end) {
			if (d[start] == n)
				return start;
			else
				return -1;
		}
		int mid = (end - start) / 2;
		end = mid - 1;
		if (d[end] < d[start]) {
			// TODO: For a shifted sub-array
			if(n == d[mid]) return mid;
			if (n < d[mid] && n < d[start]) {
				return shiftArraySearch(n, d, mid + 1, end);
			} else if (n < d[mid] && n > d[start]) {
				return shiftArraySearch(n, d, start, mid - 1);
			} else if (n > d[mid] && n < d[end]) {
				return shiftArraySearch(n, d, mid + 1, end);
			} else if (n > d[mid] && n > d[end]) {
				return shiftArraySearch(n, d, start, mid - 1);
			} else {
				return -1;
			}
		} else {
			if (n < d[mid]) {
				return shiftArraySearch(n, d, start, mid - 1);
			} else if (n > d[mid]) {
				return shiftArraySearch(n, d, mid + 1, end);
			} else {
				return mid;
			}
		}
	}

	private static int binarySearch(int n, int[] d) {
		return -1;
	}
}
